﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm
{
    class MatrixShort
    {
        public MatrixShort()
        {
            int n = GetConsole.GetInt();
            int[,] mat = new int[n,n];
            for (int y = 0; y < n; y++)
            {
                for (int x = 0; x < n; x++)
                {
                    mat[x, y] = GetConsole.GetInt();
                }
            }
            int[,] sumMat = new int[n, n];
            
            sumMat[0, 0] = mat[0, 0];

            //1행 1열 Data 구성
            for (int i = 1; i < n; i++)
            {
                sumMat[i, 0] = sumMat[i - 1, 0] + mat[i, 0];
                sumMat[0, i] = sumMat[0, i - 1] + mat[0, i];
            }

            for (int y = 1; y < n; y++)
            {
                for (int x = 1; x < n; x++)
                {
                    int minValue1 = sumMat[x - 1, y] + mat[x, y];
                    int minValue2 = sumMat[x, y - 1] + mat[x, y];
                    if (minValue1 > minValue2)
                    {
                        sumMat[x, y] = minValue2;
                    }
                    else
                    {
                        sumMat[x, y] = minValue1;
                    }
                }
            }
            Console.WriteLine(sumMat[n-1, n-1]);
            GetConsole.GetInt();
        }
    }
}
